package com.lhcai.lc.other;

/**
 * @author lhcstart
 * @create 2023-02-25 21:29
 */


/**
 * 零钱兑换
 * <p>
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 * 你可以认为每种硬币的数量是无限的。
 */
public class lc322 {
    public static void main(String[] args) {
        lc322 lc322 = new lc322();
        int i = lc322.coinChange(new int[]{1,2,5}, 11);
        System.out.println(i);
    }


    int[] memo;

    public int coinChange(int[] coins, int amount) {
        if (coins.length == 0) {
            return -1;
        }
        memo = new int[amount];
        return findWay(coins, amount);

    }

    // memo[n] 表示钱币n可以被换取的最少的硬币数，不能换取就为-1
    // findWay函数的目的是为了找到 amount数量的零钱可以兑换的最少硬币数量，返回其值int
    public int findWay(int[] coins, int amount) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }

        // 记忆化的处理，memo[n]用赋予了值，就不用继续下面的循环
        // 直接的返回memo[n] 的最优值
        if (memo[amount - 1] != 0) {
            return memo[amount - 1];
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {

           int  res = findWay(coins, amount - coins[i]);

           if (res >= 0 && res < min) {
                min = res + 1;// 加1，是为了加上得到res结果的那个步骤中，兑换的一个硬币
            }
        }

        memo[amount-1] = (min == Integer.MAX_VALUE ? -1 : min);

        return memo[amount-1];

    }

}
